閱讀前，建議可以參考Day1：閱讀指南＆為何選擇這個題目？

▌挑戰簡介

• 題目：計算機概論Ｘ30天

• 挑戰內容：連續30天紀錄計算機概論、離散數學、演算法、資料結構等課程，還有自己學習程式的心得體悟。

• 本篇性質：

  • 適合的人：對密碼學、大數處理有興趣的人，因為模數運算（mod）、費馬小定理很常拿來用
  • 一定要讀過Day 14:[離散數學]同餘（Mod）是什麼？

▌會用到的性質

一定要至少明白下面mod的性質，不然無法理解本篇內容！！

• 同餘的因數定理：a ≡ b (mod k) <=> k | a-b
• 同餘的加法性質：a ≡ b (mod k) ＆ c ≡ d (mod k) <=> a+c = b+d (mod k)
• 同餘的相乘性質：a ≡ b (mod k) ＆ c ≡ d (mod k) <=> ac = bd (mod k)
  • a ≡ b (mod k) <=> a^n ≡ b^n (mod k)
  • a ≡ b (mod k) <=> am ≡ bm (mod k)

▌費馬小定理

假如 a是一個整數，p是一個質數，且a,p互質

gcd(a,p)=1 //表示a,p互質

那麼下式一定成立

a^(p-1)≡1  mod P  // 如果 gcd(a,p)=1 且 p 為質數

比如說 4,5，其中5是質數，且gcd(4,5)=1

那

4^(5-1)≡1  mod 5
256≡1  mod 5

▌費馬小定理可以幹嘛？

所以勒，費馬小定理可以衝三小？—— 可以處理大數字！

（例題1）2^100 除以13 餘數是多少？

比如說：2^100 除以13餘數是多少？這誰知道啊，鬼才有時間慢慢乘
這時候就可以使用費馬小定理！

因為13是質數，而且qcd(2,13)=1
那根據費馬小定理 a^(p-1)≡1 mod P
我們可以推出 2^12 ≡1 mod 13

(2^12)8 X 2^4  // 把2^100 拆除成這樣 
(2^12)8 ≡1^8  mod 13 // 根據同餘的相乘-次方性質
(2^12)8  X 2^4 ≡1^8  X 2^4 mod 13  // 根據同餘的相乘性質
(2^12)8  X 2^4 ≡16 mod 13 
(2^12)8  X 2^4 ≡3 mod 13 

因此2^100除以13是多少？ 就是3

▌注意：偽質數

a^(p-1)≡1  mod P  // 如果 gcd(a,p)=1 且 p is 質數

只要 p 質數，則a^(p-1)≡1 mod P 一定成立

但是 P 未必要是質數，則a^(p-1)≡1 mod P 一定成立

比如說 P 如果是 341（他是11X31） 則 a^340 ≡1 mod 341 也會成立

此時 P 被稱為 「偽質數」

質數一定符合a^(p-1)≡1 mod P，但是未必要是質數也可以符合

▌結論

• 費馬小定理：a^(p-1)≡1 mod P // 如果 gcd(a,p)=1 且 p 為質數
• 費馬小定理可以處理很複雜的大數
• 質數帶進去一定符合a^(p-1)≡1 mod P，但是未必要是質數也可以符合費馬小定理公式（像是偽質數）

▌參考資料

• Fermat 小定理證明的事先小觀察